package com.elementum.olegomatic.matcher;

import java.io.FileReader;
import java.util.*;

public class ElementumMatcher {
	
	private SubSet[] map = new SubSet[900];
	

    public ElementumMatcher(Collection<String> dictionary) {

        for(int i = 0; i < 900; i++) {
            map[i] = new SubSet();
        }

        int count = 0;

        // (1) pre-process input dictionary
        for(String w : dictionary ) {

            count++;

            String word = w.toLowerCase();

            //if ( word.length() < 30 )
            //	out.println( word );

            //System.out.println(word);

            long sign = computeSig(word);

            int l = word.length();

			boolean bad = false;
			for(char c : word.toCharArray()) {
				int indx = c-'a';
				if ( indx < 0 || indx > 25) {
					System.out.println("bad word: " + word);
					bad = true;
				}
			}
            if ( bad ) {
                continue;
            }

            int indx = word.charAt(0)-'a';

            for(int n = l-1; n <= l+1; n++) {
                SubSet sub = map[indx*30+n];
                sub.bytes.add( sign );
                sub.words.add( word );
            }

        }

        System.out.println("count = " + count);


        int i1 = 0;
        int i2 = 0;

        for(int n = 0; n < 900; n++) {
            //int sum = 0;
            //int zero = 0;

            SubSet sub = map[n];
            List<Long> signList = sub.bytes;
            List<String> wordList = sub.words;

            List<Integer> list = new ArrayList<Integer>();

            int M = signList.size();

            int[] next = new int[M];
            Set<Integer> pool = new HashSet<Integer>();
            for(int i = 0; i < M; i++) {
                next[i] = 0;
                pool.add(i);
                list.add(i);
            }


            for(int i = 0; i < M; i ++) {

                if ( next[i] == 1 )
                    continue;

                long sig = signList.get(i);

                sub.bytes1.add( sig );

                List<Long> list2 = new ArrayList<Long>();
                sub.bytes2.add( list2 );

                List<String> list2w = new ArrayList<String>();
                sub.words2.add( list2w );


                //74297
                Set<Integer> p2 = new HashSet<Integer>();

                for(int j = i; j < M; j ++) {

                    i1++;
                    if (  next[j] == 1 ) {
                        continue;
                    }
                    i2++;

                    long sig2 = signList.get(j);

                    if (  bitcount(sig ^ sig2, 4) ) {
                        continue;
                    }

                    list2.add( sig2 );
                    list2w.add( wordList.get(j) );

                    next[j] = 1;
                }

                //sum += list2.size();


                //if ( list2.size() == 1)
                //    zero++;

                //System.out.println( list2w );
                //System.out.println(i + " " + list.size() + " " + Arrays.toString(next));

            }

        }

    }
	
	/**
     * computes signature (key) for a word. Long 64 bits - each bit corresponds to an
     * english alphabet letter. If a letter is contained twice - the corresponding bit
     * in the second half is set.
	 */
	private static long computeSig(String word) {
		long a = 0;
		char[] chars = word.toCharArray();
		for(char c : chars) {
			int indx = c-'a';
			if ( indx < 0 || indx >= 32)
				indx = 26;
			
			boolean one = (a & (1L << indx)) == 0;
			a = a | (1L << ( one ? indx : indx + 32 ));
		}
		a = a | (1L << 63);
		return a;
	}


    /**
     * efficient method to determine number of "1" bits in a long number
     *
     * @param n - input number
     * @param max - number of "1" bits
     * @return
     */
	private static boolean bitcount(long n, int max)
	{
	   int ret=0;
	   while (n!=0)
	   {
	       n&=(n-1);
	       ret++;
	       if ( ret > max)
	    	   return true;
	   }
	   return false;
	}
	


    /**
     * returns a list of matching words from the dictionary withing Levinstein distance 1
     *
     * return NULL if invalid characters
     *
     * @param w String
     * @return
     */
	public List<String> getCorrections(String w) {

        w = w.toLowerCase();
        // only lower case english characters
        for(char c : w.toCharArray()) {
            int indx = c-'a';
            if ( indx < 0 || indx > 25) {
                return null;
            }
        }


		long sig1 = computeSig(w);
		List<String> m1 = new ArrayList<>();

		int l =  w.length();
		int indx = w.charAt(0)-'a';

        // (1) get matching "subsets"
		SubSet sub = map[indx*30+l];
		
		for(int p = 0; p < sub.bytes1.size(); p++) {
			
			long sig0 = sub.bytes1.get(p);
			
			//max++;
			

			if (  bitcount(sig0 ^ sig1, 6) )
				continue;
			
			List<Long> list2 = sub.bytes2.get(p);
			
			for(int m = 0; m < list2.size(); m++) {
			
				long sig2 = list2.get(m);
			
				if( bitcount(sig1 ^ sig2, 2) )
					continue;
			
				//max++;
			
				//if ( d <= 2 ) {
					//max ++;
					List<String> list2w = sub.words2.get(p);
					String root = list2w.get(m);
				
					int L = LevenshteinDistance(root, w);
					//System.out.println("root = " + root + " " + L);
				
					if ( L <= 1 ) {
						m1.add(  root );
					}
				
				//}
			}
		}
		//return (m1.size() > 0 ? m1 : m2);
		Collections.sort(m1);
		return m1;
	}
	
	
	public List<String> getCorrectionsBrute(String w) {
		List<String> m1 = new ArrayList<String>();
		List<String> all = map[(w.charAt(0)-'a')*30 + w.length()].words;
		for(String w2 : all) {
			if(LevenshteinDistance(w, w2) <= 1)
				m1.add(w2);
		}
		Collections.sort(m1);
		return m1;
	}


    /**
     * determines the distance between two words - from Wikipedia
     *
     * @param s
     * @param t
     * @return
     */
	private static int LevenshteinDistance(String s, String t) {
	    // degenerate cases
	    if (s == t) return 0;
	    if (s.length() == 0) return t.length();
	    if (t.length() == 0) return s.length();
	 
	    // create two work vectors of integer distances
	    int[] v0 = new int[t.length() + 1];
	    int[] v1 = new int[t.length() + 1];
	 
	    // initialize v0 (the previous row of distances)
	    // this row is A[0][i]: edit distance for an empty s
	    // the distance is just the number of characters to delete from t
	    for (int i = 0; i < v0.length; i++)
	        v0[i] = i;
	 
	    for (int i = 0; i < s.length(); i++)
	    {
	        // calculate v1 (current row distances) from the previous row v0
	 
	        // first element of v1 is A[i+1][0]
	        //   edit distance is delete (i+1) chars from s to match empty t
	        v1[0] = i + 1;
	 
	        // use formula to fill in the rest of the row
	        for (int j = 0; j < t.length(); j++)
	        {
	            int cost = (s.charAt(i) == t.charAt(j)) ? 0 : 1;
	            v1[j + 1] = Math.min(v1[j] + 1, Math.min( v0[j + 1] + 1, v0[j] + cost) );
	        }
	 
	        // copy v1 (current row) to v0 (previous row) for next iteration
	        for (int j = 0; j < v0.length; j++)
	            v0[j] = v1[j];
	        
	    }
	 
	    return v1[t.length()];
	}
	

    /**
     * class that holds lists of words withing the same distance from each other
     * the structure is a little convoluted - but this is for performance
     */
	private static class SubSet {
		List<String> words = new ArrayList<>();
		List<Long> bytes = new ArrayList<>();
		
		List<Long> bytes1 = new ArrayList<>();
		
		List<List<String>> words2 = new ArrayList<>();
		List<List<Long>> bytes2 = new ArrayList<>();
	}


}

